package com.leetcode.offer.chapter5;

/**
 * @author Dennis Li
 * @date 2020/7/17 19:15
 */
public class TwoSum_57 {
    public int[] twoSum(int[] nums, int target) {
        // 先查找到target的位置
        //int i = 0, j = binary(nums, target);
        int i = 0, j = nums.length - 1;
        while (nums[i] + nums[j] != target) {
            if (nums[i] + nums[j] > target) {
                j--;
                // 为了减少i后退的步数，不用i = 0
                i = i > 0 ? i - 1 : 0;
            } else {
                i++;
            }
        }
        return new int[]{nums[i], nums[j]};
    }

    public int binary(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int mid = (i + j) >> 1;
            if (nums[mid] > target) j = mid - 1;
            else if (nums[mid] < target) i = mid + 1;
            else return mid;
        }
        return i;
    }

}
